1. Field of the Invention
The present invention relates to a modular multiplication method and the system for executing modular multiplication such as A.times.B modulo (referred to as mod, hereinafter) N at high speed, where A denotes a multiplicand; B denotes a multiplier and N denotes a modulus. The present invention is effectively available for cryptographic and authentic systems or technique, because modular exponentiation (power multiplication) such as M.sup.e mod N (where e denotes the exponent) can be executed in the same way as A.times.B mod N.
2. Description of the Prior Art
In the conventional method of modular multiplication A.times.B mod N, in general as shown in FIG. 1(A), after A.times.B has been calculated, the calculated A.times.B is divided by N to obtain a remainder as its calculation result. In this drawing, the multiplication is executed by shifting the multiplicand A bit by bit toward the most significant bit direction for multiply addition on the basis of a radix 2, and the division is executed in the same way by shifting the modulus N in the opposite direction for division subtraction. Therefore, when the number n of bits is determined in binary notation of A, B and N, n-time multiply additions of partial products (A or O) are required for the multiplication at its maximum and further n-time division subtractions of modular subtracters (N or O) are required for the division at its maximum. Further, FIG. 1(A) shows an example of 7-bit binary numbers, in which A/O represents A or O.
In this conventional method, although subtractions are repeated for division, since the modular subtracters are not previously determined, it has been necessary to compare each partial remainder with the modulus N for each partial subtraction operation, so that the divisional operation is not effective and therefore the computational speed is low.
Further, when the conventional method is executed by a general purpose computer, since each number A, B or N is divided into the unit number of bits (digits) (e.g. 32 bits) before repeating the additions and subtractions, the number of the additions and subtractions further increases. As a result, when the number of bits (digits) n increases, there exists a problem in that the divided intermediate results must be stored in a great number of registers, so that it has been difficult to execute the computation (calculation) at high speed. In this connection, although it is possible to improve the computational speed by executing a multiplication after the bits have been divided into the number of a processing unit of the multipliers incorporated in the general purpose computer, there still exists a problem in that the number of access to memory increases and therefore the computational speed is still low.
Further, where specialized circuits which can simultaneously process many bits are incorporated, although the computational speed can be improved, there arises another problem in that hardware of 2n-bit length is required and therefore the hardware efficiency is not high.
To improve the low hardware efficiency of the conventional divisional operation, a method of decreasing the number of additions and subtractions related to divisional operations with reference to a remainder reference table has been proposed. The above-mentioned method of using a remainder reference table is to transform a multiplication result represented by several higher significant bits into a remainder represented by lower significant bits after a 2n-bit multiplication result has been obtained. For instance, in the case of 4-bit unit, remainders by divisors or moduli N of 0001.times.2.sup.n, 0010.times.2.sup.n, . . . 1111.times.2.sup.n are previously listed in a remainder reference table, and the multiplication result can be obtained by adding a value obtained by removing 4 higher significant bits to the remainder represented by the 4 higher significant bits, in order to reduce the number of bits one by one, and the computational processing is completed when the n-bit multiplication result has been obtained.
In this method, however, the speed of the multiplication operation is not improved. Further the remainder reference table inevitably increases the memory capacity to store the table. Additionally, since n-bit remainder table data are transferred to or from calculators; the calculating speed is not high and the circuit volume is large; and further the control is rather complicated. In other words, there exist serious problems with the computational speed, hardware volume, and circuit design complication.
To overcome the problems involved when multibit specialized circuits are incorporated in the conventional method, Baker has proposed a method of using specialized circuits by interposing modular subtracters between two multiply additions, so that the operation can be executed by only n-bit length specialized circuits, as disclosed by "Fast Computation of A*B Modulo N", by P. W. Baker, Electron Letter, Vol. 23, No. 15, pp 794-795 (1987).
In this Baker method, as shown in FIG. 1(B), n-bit partial products and n-bit partial modular subtracters are added or subtracted in sequence beginning from the most significant bits. The partial products are determined by taking bit by bit the multiplier B from the most significant bit and by adding A or O to the partial remainder. On the other hand, -2N, -N, O, N, or 2N modular subtracters are determined according to the value of the partial remainder and then added to the partial remainder. The partial remainder is shifted one bit toward the most significant bit side, and the above operations are repeated. In this Baker method, although the multiplication is executed on the basis of a radix number 2 bit by bit, the division is executed on the basis of a radix number 4 within a range from -2N to 2N in order to prevent the partial remainders from overflowing from the n-bits length computational range.
This Baker method can solve the problem involved in the specialized circuits; however, the computational speed is not improved because the number of additions and subtractions cannot be reduced markedly in comparison with the conventional method.
As described above in the prior-art methods, there exist various problems with respect to the computational speed, hardware volume, circuit design complication, etc.